The present invention relates in general to buffer management in networking systems, and more particularly to a two-dimensional link list data structure for queuing and de-queuing packets.
The need for faster communication among computers and other systems requires ever faster and more efficient networks. Today, networks typically use an amalgam of various software and hardware to implement a variety of network functions and standards. Network devices such as client computer systems, servers, hubs, routers, switches, network backbones, etc., are each complex devices that require digital processing in hardware and software to facilitate network communication. Some tasks performed in a network device include translation between different network standards such as Ethernet and Asynchronous Transfer Mode (ATM), reformatting of data, traffic scheduling, routing of data cells, packets messages, etc. Depending on the particular protocol being implemented, some tasks may be performed at different points in the network. Also, because of the need for compatibility, flexibility and making changes to network functionality, much of today""s network processing is implemented in software which is relatively slow compared to the bandwidth demanded by the network and applications running on the network. For example, the Layer 3 and Layer 4 functions of the OSI 7-Layer Model are typically implemented in software running on one or more devices on the network.
Network system performance is greatly affected by device architectures and CPU bandwidth. In conventional networking devices, for example, the main CPU implements software to queue a packet into a packet link list. This degrades CPU performance, especially where there is a high volume of data traffic, as the CPU is required to oversee and implement processor intensive data buffering and transfer functions. This also results in increased memory access times, which degrades data transfer speed and network efficiency. Furthermore, in conventional networking systems, only one packet is processed at a time, which can lead to slow throughput due to inefficient memory allocation and access techniques. In network systems where a variety of data packet types and sizes are processed, memory access and allocation can be a serious problem.
Some network systems use a link-list data structure for queuing and de-queuing packets. However, these systems typically require a two-stage lookup in an off-chip memory to determine which packets are to be de-queued. This results in slow throughput and increased processor use, thereby resulting in less than optimal performance.
The present invention provides novel systems and methods for queuing and de-queuing packets in a two-dimensional link list data structure. A network processor receives data for transmission for a plurality of Virtual Connections (VCs). The processor reassembles data cells and frames into data packets and creates a two-dimensional link list data structure for each VC. The data field of each data packet is stored in one or more buffer memories. Each buffer memory has an associated buffer descriptor that includes a pointer to the location of the buffer memory, and a pointer pointing to the memory location of the next buffer descriptor associated with a buffer memory storing data for the same packet. Each data packet also has an associated packet descriptor including a pointer pointing to the memory location of the first buffer descriptor associated with that packet, and a pointer pointing to the memory location of the packet descriptor associated with the next data packet queued for transmission. A VC descriptor for each VC keeps track of the memory locations of the next packet descriptor and the next buffer descriptor to be de-queued, and the memory locations for storing the next packet descriptors and the next buffer descriptors to be queued. The two-dimensional link list data structure of the present invention allows for a one-stage look-up in an internal memory.
According to an aspect of the invention, a method is provided for queuing one or more data packets for transmission for a virtual connection (VC) in a networking system device having an internal memory, wherein each of the data packets has a data field. The method typically comprises the step of creating a VC queue descriptor associated with a first VC. The VC queue descriptor typically includes first, second, third and fourth pointers pointing to first, second, third and fourth memory spaces, respectively, wherein each of the first, second, third and fourth pointers has a value indicating the location of the associated memory space. The method also typically includes the steps of storing a first packet descriptor associated with a first one of the packets to the first memory space such that the first pointer points to the first packet descriptor, the first packet descriptor including a next packet descriptor pointer pointing to the third memory space, and a buffer descriptor pointer pointing to the second memory space; and storing a first buffer descriptor to the second memory space such that the second pointer points to the first buffer descriptor, the first buffer descriptor including a next buffer descriptor pointer pointing to the fourth memory space, and a buffer pointer pointing to a first buffer memory space, wherein at least a first portion of the data field of the first packet is stored in the first buffer memory space.
According to another aspect of the invention, a method is provided for de-queuing one or more data packets queued for transmission in a data structure for a virtual connection (VC) in a networking system device, wherein each data packet has a data field. The data structure typically includes a packet descriptor associated with each of the packets, and one or more buffer descriptors associated with each of the packets, wherein each buffer descriptor includes a buffer pointer pointing to a buffer memory. The method typically comprises the steps of reading a next packet descriptor pointer in a VC queue descriptor associated with a first VC to determine the memory location of a first packet descriptor associated with a first packet to be de-queued, wherein the next packet descriptor pointer has a value indicating the memory location of the first packet descriptor; reading the first packet descriptor, wherein the first packet descriptor includes a first buffer descriptor pointer having a value indicating the memory location of a first buffer descriptor associated with the first packet; reading the first buffer descriptor to determine the memory location of a first buffer memory to be de-queued, wherein the first buffer descriptor includes a first buffer pointer having a value indicating the location of the first buffer memory; and de-queuing the data stored in the first buffer memory.
According to yet another aspect of the present invention, a network processor in a networking accelerator system is provided, wherein the network processor is communicably coupled to one or more networks. The network processor typically comprises an internal memory, and processing logic for implementing a two-dimensional queuing and de-queuing method for queuing and de-queuing packets for transmission in a two-dimensional link list data structure for one or more Virtual Connections (VCs). The network processor is preferably integrated on a single chip, but may be integrated on many chips.
According to a further aspect of the invention, a method is provided for implementing a two-dimensional link list data structure for use in queuing and de-queuing packets for transmission for one or more Virtual Connections (VCs) in a network processor communicably coupled to one or more networks, wherein the network processor has an internal memory. The network processor is preferably integrated on a single chip, but may be integrated on many chips. The method typically comprises the steps of: building the two-dimensional link list data structure for the one or more VCs, wherein the data structure includes a first list linking one or more buffer descriptors on a per-packet basis, and a second list linking one or more packet descriptors on a per-VC basis; and storing at least a portion of the data structure to the internal memory.
According to yet a further aspect of the invention, a method is provided in a networking system device for queuing one or more data packets for transmission for a virtual connection (VC), wherein each of the data packets has a data field. The method typically comprises the steps of creating a VC queue descriptor associated with a first VC, wherein the VC queue descriptor typically includes a first pointer pointing to a first memory space; a second pointer pointing to a second memory space; a third pointer pointing to a third memory space; and a fourth pointer pointing to a fourth memory space. Each of the first, second, third and fourth pointers has a value indicating the location of an associated memory space. The method also typically includes the step of storing a first packet descriptor associated with a first one of the packets to the first memory space such that the first pointer points to the first packet descriptor, wherein the first packet descriptor includes a next packet descriptor pointer pointing to the third memory space, and a buffer pointer pointing to a first buffer memory space, wherein the entire data field of the first packet is stored in the first buffer memory space.
According to an additional aspect of the invention, a method is provided in a network device for de-queuing one or more data packets queued for transmission in a data structure for a virtual connection (VC). Each data packet has a data field, and the data structure includes a packet descriptor associated with each of the packets, and one or more buffer memories associated with each of the packets. Each of the packets has one or more associated buffer descriptors only if more than one buffer memory is associated with the packet, and each buffer descriptor includes a buffer pointer pointing to one of the buffer memories. The method typically comprises the step of reading a next packet descriptor pointer in a VC queue descriptor associated with a first VC to determine the memory location of a first packet descriptor associated with a first packet to be dequeued, wherein the next packet descriptor pointer has a value indicating the memory location of the first packet descriptor. The method also typically includes the steps of reading the first packet descriptor, wherein the first packet descriptor includes a flag indicating that only one buffer memory is associated with the first packet, and a first buffer pointer having a value indicating the location of a first one of the buffer memories; and de-queuing the data stored in the first buffer memory.